package org.leetcode.hard.leetcode115;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public int numDistinct2(String s, String t) {
        int n1 = s.length();
        int n2 = t.length();

        int[][] dp = new int[n1 + 1][n2 + 1];

        //将dp的第一列中的元素设置为1，即t为空字符串，求s的子序列等于空字符串的数量
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    //dp[i-1][j-1]表示：当前i和j的指向的字符相同，选择i指向的元素，那么dp[i][j]的值就是前一个的值
                    //dp[i-1][j]表示：当前i和j的指向的字符相同，可以不选择i指向的元素，那么dp[i][j]的值就是不考虑当前i的值
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    //求的是s的子序列中t的数量，所以t是不变的
                    //i和j指向的字符不相同，需要忽略当前i指向的字符
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n1][n2];
    }


    //回溯 超时
    public int numDistinct(String s, String t) {

        backtracking(s, t, 0);

        for (String str : list) {
            if (str.equals(t)) {
                count++;
            }
        }

        return count;
    }

    List<String> list = new ArrayList<>();
    StringBuilder temp = new StringBuilder();
    int count = 0;

    private void backtracking(String s, String t, int startIndex) {

        if (temp.length() >= t.length()) {
            list.add(new String(temp));
        }

        if (startIndex >= s.length()) {
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            temp.append(s.charAt(i));

            backtracking(s, t, i + 1);

            temp.deleteCharAt(temp.length() - 1);
        }
    }

    public static void main(String[] args) {
        Solution test = new Solution();
        int i = test.numDistinct("babgbag", "bag");
        System.out.println(i);
    }
}
